package com.ly.algorithm.leetcode.tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Classname Problem652
 * @Description
 *
 * 给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
 *
 * 两棵树重复是指它们具有相同的结构以及相同的结点值。
 *
 * 示例 1：
 *
 *         1
 *        / \
 *       2   3
 *      /   / \
 *     4   2   4
 *        /
 *       4
 * 下面是两个重复的子树：
 *
 *       2
 *      /
 *     4
 * 和
 *
 *     4
 *
 * @Date 2020/12/22 19:51
 * @Author 冷心影翼
 */
public class Problem652 {

	public static void main(String[] args) {
		TreeNode treeNode = new TreeNode(1);
		treeNode.left = new TreeNode(2);
		treeNode.left.left = new TreeNode(4);
		treeNode.right = new TreeNode(3);
		treeNode.right.left = new TreeNode(2);
		treeNode.right.left.left = new TreeNode(4);
		treeNode.right.right = new TreeNode(4);
		Solution652 solution652 = new Solution652();
		solution652.findDuplicateSubtrees(treeNode);
	}
}


class Solution652 {

	Map<String,Integer> map = new HashMap<>();

	List<TreeNode> ans = new ArrayList<>();

	public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
		serial(root);
		return ans;
	}

	public String serial(TreeNode treeNode) {
		if(treeNode == null)
			return "#";
		String serial = treeNode.val +" "+ serial(treeNode.left) +" "+ serial(treeNode.right);
		map.put(serial,map.getOrDefault(serial,0)+1);
		if( map.get(serial)== 2) {
			ans.add(treeNode);
		}
		return serial;
	}
}